package com.le.basic.subArrayProblem;

import org.junit.Test;

/**
 * 给定一个数组arr，值可正，可负，可 0；一个整数aim，求累加 和[小于等于]aim的，最长子数组，
 * 要求时间复杂度O(N)
 */
public class Code_05_LongestSubarrayLessSumAwesomeSolution {
    // 思路
    // 1. 先求每个位置的最小累加和,及终止下标
    // 2. 在判断累加和是否小于aim
    public static int process(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 从右向左统计最小累加和
        int[] minSums = new int[arr.length];
        // 从右向左统计最小累加和下标
        int[] minSumEnds = new int[arr.length];
        minSums[arr.length - 1] = arr[arr.length - 1];
        minSumEnds[arr.length - 1] = arr.length - 1;
        for (int i = arr.length - 2; i >= 0; i--) {
            minSums[i] = minSums[i + 1] < 0 ? arr[i] + minSums[i + 1] : arr[i];
            minSumEnds[i] = minSums[i + 1] < 0 ? minSumEnds[i + 1] : i;
        }
        int end = 0; // 当前i位置累加和大于aim的位置
        int sum = 0;
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            // while循环结束之后：
            // 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
            // 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
            while (end < arr.length && sum + minSums[end] <= aim) {
                sum += minSums[end];
                end = minSumEnds[end] + 1;
            }
            // 统计当前位置长度
            res = Math.max(res, end - i);
            if (end > i) {
                sum -= arr[i]; // 累加和剔除当前位置的值
            } else { // 窗口内已经没有数了，说明从i开头的所有子数组累加和都不可能<=k
                end = i + 1;
            }
        }
        return res;
    }


    @Test
    public void test() {
        int[] arr = {2, 4, 4, -2, 1, -2};
        System.out.println(process(arr, 2));
    }
}
